# Leetcode140算法复杂度分析
# 时间复杂度：O(N^2 * 2^N)，在最坏的情况下，其中N是字符串的长度。这是一个粗略的上限，实际性能取决于字典和字符串的具体内容。
# 空间复杂度：O(N * 2^N)，存储所有可能的句子。

import matplotlib.pyplot as plt
from alg import Solution
import numpy as np
import time
import random
import string

# 基础算法正确性检验
def check_correctness():
    so = Solution()
    test_cases = [
        (("catsanddog", ["cat", "cats", "and", "sand", "dog"]), sorted(["cats and dog", "cat sand dog"])),
        (("pineapplepenapple", ["apple", "pen", "applepen", "pine", "pineapple"]), sorted(["pine apple pen apple", "pineapple pen apple", "pine applepen apple"])),
        (("catsandog", ["cats", "dog", "sand", "and", "cat"]), []),
        (("a", ["a"]), ["a"]),
        (("ab", ["a", "b"]), ["a b"])
    ]
    for i, ((s, wordDict), expected) in enumerate(test_cases):
        result = so.wordBreak(s, wordDict)
        print(f"用例{i+1}: 输入 s='{s}', wordDict={wordDict}，期望输出={expected}，实际输出={sorted(result)}", end=' ')
        # 对结果进行排序，因为返回句子的顺序不重要
        if sorted(result) == expected:
            print("✅ 通过")
        else:
            print(f"❌ 未通过: 期望={expected}，实际={sorted(result)}")
            assert False

class test_Leetcode140:
    so = Solution()

    lengths = [16, 32, 64, 128, 256, 512]
    times = []
    
    # 固定的词典，用于生成测试用例
    wordDict = ['a', 'b', 'c']

    def normalization(ref, base):
        # 使用第一个点进行归一化，以对齐曲线的起点
        return [x / ref[0] * base[0] for x in ref]

    n = np.array(lengths, dtype=np.float64)
    n2 = n ** 2
    n_log = n * np.log2(n + 1) # 使用 n/2 作为基数以更好地拟合

    for length in lengths:
        # 通过重复拼接词典中的词来构造测试字符串
        s = "".join(random.choices(wordDict, k=length))
        
        start_time = time.perf_counter()
        so.wordBreak(s, wordDict)
        end_time = time.perf_counter()
        
        elapsed_time = end_time - start_time
        times.append(elapsed_time)
        print(f"长度为{length}的测试用例，运行时间为{elapsed_time:.6f}秒")

    plt.figure(figsize=(10, 6))
    plt.plot(n, times, 'bo-', label="Measured Time", linewidth=2)
    plt.plot(n, normalization(n2, times), 'r--', label="O(n^2)", linewidth=2)
    plt.plot(n, normalization(n_log, times), 'g--', label="O(nlogn) Scaled", linewidth=2)
    plt.plot(n, normalization(n, times), 'm--', label="O(n) Scaled", linewidth=2)

    # 使用对数刻度可以更好地观察指数增长
    plt.yscale('log')
    
    plt.xlabel('Length of input string')
    plt.ylabel('Run Times (seconds, log scale)')
    plt.title('Leetcode140 Performance Analysis')
    plt.grid(True)
    plt.legend()
    plt.tight_layout()
    plt.show()
    plt.savefig('Leetcode140.png')

if __name__ == "__main__":
    print("基础算法正确性检验：")
    check_correctness()
    print("\n开始性能分析：")
    test = test_Leetcode140()
